package com.zdp.leetcodeMiddle;

import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），
* 整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，
* 但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
0 <= s.length <= 3000
s 仅由数字组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 复原IP地址_93 {
    public static void main(String[] args) {
        复原IP地址_93 demo = new 复原IP地址_93();
        demo.restoreIpAddresses(new String("101023"));
        for(String s:demo.result){
            System.out.println(s);
        }
    }


    /*
    * 解题思路：
    * 回溯，遍历所有的可能性+剪枝（去除掉一些不可能的结果）
    * */
    private List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if(s.length()<4){
            return result;
        }
        char[] ss = s.toCharArray();
        List<String> temp = new ArrayList<>();
        f(0,ss,temp);
        return result;
    }

    public void f(int index,char[] s,List<String> temp){
        if(temp.size()==4&&index<s.length){
            return;
        }
        if(index>=s.length){ // 字符串遍历到头了
            if(temp.size() == 4){
                StringBuilder f = new StringBuilder();
                for(int i=0;i<temp.size();i++){
                    if(i==0)
                        f.append(new String(temp.get(i)));
                    else
                        f.append(new String("."+temp.get(i)));
                }
                result.add(f.toString());
            }
            return ;
        }
        StringBuilder num = new StringBuilder();
        for(int i = index;i<index+3&&i<s.length;i++){
            // 截取 1 个 2 个 3 个
            if(i!=index && s[index] == '0'){
                return;
            }
            num.append(s[i]);
            int nums = Integer.valueOf(num.toString());
            if(nums>255){
                return;
            }
            temp.add(num.toString());
            f(i+1,s,temp);
            // 回溯
            temp.remove(temp.size()-1);
        }
    }
}
